#include "../tools.h"


class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int me = nums[0];
        int ne = 1;
        for(int i = 1; i < nums.size(); ++i){
            if(ne == 0){
                me = nums[i];
                ne = 1;
                continue;
            }

            if(nums[i] == me){
                ++ne;
            }else{
                --ne;
            }
        }

        if(ne == 0) return -1;
        ne = 0;
        for(int i = 0; i < nums.size(); ++i){
            if(nums[i] == me) ++ne;
        }
        if(ne > (nums.size() / 2)) return me;
        return -1;
    }
};

int main(int argc, char const *argv[])
{
    
    // vector<int> v = {3,2};//{1,2,5,9,5,9,5,5,5};
    // vector<int> v = {2,2,1,1,1,2,2};
    // vector<int> v = {1,2,3};

    Solution s;

    cout << s.majorityElement(v);
    return 0;
}
